import collections
class Solution(object):
    def reorganizeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        c = collections.Counter(s)
        t = max(c.values())
        if t <= (len(s) + 1) // 2:
            m = [[c[key], key] for key in c]
            m.sort(reverse=True)
            D = [[m[0][1]] for _ in range(m[0][0])]
            index = 0
            for i in range(1, len(m)):
                for _ in range(m[i][0]):
                    D[index % t].append(m[i][1])
                    index += 1
            return ''.join([''.join(P) for P in D])
        else:
            return ''


data = Solution()
s = "aabbccddddd"
print(data.reorganizeString(s))
